package practice_2025_7_10;

import java.util.ArrayList;

public class Solution {
    /**
     * 排序数组
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort(int[] nums, int begin, int end) {
        // System.out.println("begin: " + begin + " end: " + end);
        if (begin >= end) {
            return;
        }
        int key = nums[begin];
        int left = begin, right = end + 1, cur = begin;
        while(cur < right) {
            if (nums[cur] < key) {
                swap(nums, cur, left);
                left++;
            } else if (nums[cur] == key) {
                cur++;
            } else {
                right--;
                swap(nums, cur, right);
            }
        }
        // System.out.println("key: " + key + " left: " + nums[left] + " right: " + nums[right]);
        // System.out.println(Arrays.toString(nums));
        quickSort(nums, begin, left - 1);
        quickSort(nums, right, end);
    }
    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    /**
     * 快排, 找到基准后，数组分两段，再继续排
     * @param nums
     * @param begin
     * @param end
     */
    public void quickSort1(int[] nums, int begin, int end) {
        // System.out.println("begin: " + begin + " end: " + end);
        if (begin >= end) {
            return;
        }
        int p = nums[begin];
        int left = begin, right = end;
        while(left < right) {
            while(left < right && nums[right] >= p) {
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <= p) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = p;
        quickSort(nums, begin, left - 1);
        quickSort(nums, left + 1, end);
    }


    /**
     * 数组中第 k 个最大的数
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, k);
    }
    public int find(int[] nums, int begin, int end, int k) {
        if (begin >= end) {
            return nums[begin];
        }
        int key = nums[begin];
        int left = begin - 1, right = end + 1, cur = begin;
        while(cur < right) {
            if (nums[cur] < key) {
                left++;
                swap(nums, left, cur);
            } else if (nums[cur] == key) {
                cur++;
            } else {
                right--;
                swap(nums, cur, right);
            }
        }
        // [begin, left] < key
        // [left + 1, right - 1] = k
        // [right, end] > k
        int a = end - right + 1;
        int b = a + (right - 1 - left);
        // System.out.println("left: " + left + " right: " + right + " begin: " + begin + " end: " + end);
        // System.out.println("key: " + key + " a: " + a + " b: " + b + "k: " + k);
        // System.out.println(Arrays.toString(nums));
        if (k <= a) {
            return find(nums, right, end, k);
        } else if (k <= b) {
            return key;
        } else {
            return find(nums, begin, left, (k - b));
        }
    }

    ArrayList<Integer> list = new ArrayList<>();

    /**
     * 库存管理III
     * @param stock
     * @param cnt
     * @return
     */
    public int[] inventoryManagement(int[] stock, int cnt) {
        if (cnt <= 0) return new int[]{};
        find1(stock, 0, stock.length - 1, cnt);
        int[] res = new int[cnt];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public void find1(int[] stock, int begin, int end, int cnt) {
        if (begin >= end) {
            list.add(stock[begin]);
            return;
        }
        int key = stock[begin];
        int left = begin - 1, right = end + 1, cur = begin;
        while(cur < right) {
            if (stock[cur] < key) {
                left++;
                swap(stock, left, cur);
            } else if (stock[cur] == key) {
                cur++;
            } else {
                right--;
                swap(stock, cur, right);
            }
        }
        // [begin, left] < key -> a = left - begin + 1
        // [left + 1, right - 1] = key, b = right - 1 - left
        // [right, end] > key
        int a = left - begin + 1;
        int b = right - left - 1;
        if (cnt < a) {
            find1(stock, begin, left, cnt);
        } else if (cnt <= (a + b)) {
            for (int i = begin; i < (begin + cnt); i++) {
                list.add(stock[i]);
            }
        } else {
            for (int i = begin; i < right; i++) {
                list.add(stock[i]);
            }
            find1(stock, right, end, (cnt - a - b));
        }
    }

    /**
     * 交易逆序对的总数
     * @param record
     * @return
     */
    public int reversePairs(int[] record) {
        return findPairs(record, 0, record.length - 1);
    }
    public int findPairs(int[] record, int begin, int end) {
        if (begin >= end) {
            return 0;
        }
        int mid = (begin + end) / 2;
        int count = 0;
        // 继续递归, 找到其中逆序对的个数，并排序
        count += findPairs(record, begin, mid);
        count += findPairs(record, mid + 1, end);
        // 找到合并后逆序对的个数
        // [begin, mid] [mid + 1, end]
        // 6 5 4  5 3 2
        // 6 > 5 -> (mid - left + 1)
        int[] tmp = new int[end - begin + 1];
        int cur1 = begin, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= end) {
            if (record[cur1] > record[cur2]) {
                count += (end - cur2 + 1);
                tmp[i++] = record[cur1++];
            } else {
                tmp[i++] = record[cur2++];
            }
        }
        while(cur1 <= mid) {
            tmp[i++] = record[cur1++];
        }
        while(cur2 <= end) {
            tmp[i++] = record[cur2++];
        }
        for(i = 0; i < tmp.length; i++) {
            record[i + begin] = tmp[i];
        }
        return count;
    }

    /**
     * 翻转对
     * @param nums
     * @return
     */
    public int reversePairs1(int[] nums) {
        return findReversePairs(nums, 0, nums.length - 1);
    }
    public int findReversePairs(int[] nums, int begin, int end) {
        if (begin >= end) {
            return 0;
        }
        int count = 0;
        int mid = (begin + end) / 2;
        count += findReversePairs(nums, begin, mid);
        count += findReversePairs(nums, mid + 1, end);
        int cur1 = begin, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= end) {
            if ((nums[cur1] / 2.0) > nums[cur2]) {
                count += (end - cur2 + 1);
                cur1++;
            } else {
                cur2++;
            }
        }
        // 排序
        sort(nums, begin, end, mid);
        return count;
    }

    public void sort(int[] record, int begin, int end, int mid) {
        int cur1 = begin, cur2 = mid + 1, i = 0;
        int[] tmp = new int[end - begin + 1];
        while(cur1 <= mid && cur2 <= end) {
            if (record[cur1] > record[cur2]) {
                tmp[i++] = record[cur1++];
            } else {
                tmp[i++] = record[cur2++];
            }
        }
        while(cur1 <= mid) {
            tmp[i++] = record[cur1++];
        }
        while(cur2 <= end) {
            tmp[i++] = record[cur2++];
        }
        for(i = 0; i < tmp.length; i++) {
            record[i + begin] = tmp[i];
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.sortArray(new int[] {5,1,1,2,0,0});
    }
}
